#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 103. 二叉树的锯齿形层序遍历.py
@time: 2022/1/7 16:04
@desc:
    - 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
    - https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
1. Ot(n), Os(n)
'''


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return None
        queue, res = [], []
        queue.append([root])
        step = 1
        while queue:
            level = queue.pop(0)
            next_level, temp = [], []
            while level:
                node = level.pop(0)
                temp.append(node.val)
                if node.left: next_level.append(node.left)
                if node.right: next_level.append(node.right)
            res.append(temp[::step])
            if next_level: queue.append(next_level)
            step *= -1
        return res

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# 好看一点
class Solution02(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        queue, ans = [[root]], []
        step = 1
        while queue:
            level = queue.pop(0)
            next, tmp = [], []
            for node in level:
                tmp.append(node.val)
                if node.left: next.append(node.left)
                if node.right: next.append(node.right)
            ans.append(tmp[::step])
            step *= -1
            if next: queue.append(next)
        return ans



if __name__ == '__main__':
    root = TreeNode(3, left = TreeNode(9), right=TreeNode(20, left=TreeNode(15), right=TreeNode(7)))
    Solution().zigzagLevelOrder(root)